import java.util.Arrays;
import java.util.Objects;

/**
 * 功能：
 * 作者：lc
 * 日期：2024/9/21 21:44
 */
public class Algorithm_002_2_FindLeft {
    public static void main(String[] args) {
        Integer N = 10;
        Integer V = 10;
        Integer testTime = 50000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            Integer n = (int) (Math.random() * N);
            Integer[] arr = randomArray(N, V);
            Arrays.sort(arr);
            Integer num = (int) (Math.random() * N);
            if (right(arr, num) != findLeft(arr, num)) {
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束！");
    }

    // 验证
    public static Integer[] randomArray(Integer n, Integer v) {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }

    // 对数器
    // 保证arr有序，使用该方法
    public static Integer right(Integer[] sortedArr, Integer num) {
        for (int i = 0; i < sortedArr.length; i++) {
            if (sortedArr[i] >= num) {
                return i;
            }
        }
        return -1;
    }

    // 保证arr有序，使用该方法
    // 在有序数组中找到>=num的最左位置
    public static Integer findLeft(Integer arr[], Integer num) {
        Integer l = 0, r = arr.length - 1, m = 0;
        // m=l+(r-l)/2;  防止溢出
        // m=l+((r-l)>>2);
        Integer ans = -1;
        while (l <= r) {
            m = (r + l) / 2;
            if (arr[m] >= num) {
                r = m - 1;
                ans = m;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }
}
